package base.sort.other;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 桶排序
 */
public class BucketSort {
    public List<Integer> sort(ArrayList<Integer> A) {
        // 0-99的整数
        int k = 100;
        var buckets = new ArrayList<LinkedList<Integer>>();
        var list = new ArrayList<Integer>();

        for (int i = 0; i < k; i++) {
            buckets.add(new LinkedList<>());
        }

        // 元素放在链表中
        for (var item : A) {
            buckets.get(item % k).add(item);
        }

        for (var bucket : buckets) {
            list.addAll(bucket);
        }

        return list;

    }
}
